#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 092. 反转链表 II.py
@time: 2022/1/10 16:19
@desc: https://leetcode-cn.com/problems/reverse-linked-list-ii/
> 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

@解题思路：
    1. 找到left，right两个结点，并找到left的前驱结点lpre
    2. 将[left, right]区间反转（此步可以将新的右结点链接到原right的后继结点）
    3. 将lpre链接到新的left，若lpre为None，则新的head为新的left
    4. Ot(N), Os(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def find_l_r(self, head, left, right):
        pre, p = None, head
        lpre, lt, rt = None, None, None
        count = 0
        while p:
            count += 1
            if count==left:
                lpre, lt = pre, p
            if count==right:
                rt = p
                break
            pre = p
            p = p.next
        return lpre, lt, rt

    def reverse(self, left, right):
        pre, p = None, left
        while not pre==right:
            next = p.next
            if not pre: p.next = right.next
            else: p.next = pre
            pre = p
            p = next
        # 此时新的头部还未接上
        return right, left

    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        if not head: return None
        # 找到left和right对应的结点，和left的前驱
        lpre, lt ,rt = self.find_l_r(head, left, right)
        # 反转[left, right]区间的链表
        new_lt, new_rt = self.reverse(lt, rt)

        # 接上原来的列表
        # 头
        if lpre:
            lpre.next = new_lt
        else:
            head = new_lt
        return head


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution02(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """

        def reverse(head, tail):
            pre, p = None, head
            while not pre == tail:
                next = p.next
                p.next = pre
                pre = p
                p = next
            return tail, head

        # 1. 找到left, right所在的位置，然后断链
        dummy = ListNode()
        dummy.next = head
        lpre, lp, rp = dummy, None, None
        # 定位到(left, right)区间的左边界的前一个
        for _ in range(left - 1):
            lpre = lpre.next
        lp, rp = lpre.next, lpre.next

        # 定位到右边界
        for _ in range(right - left):
            rp = rp.next

        # 2. 断链
        lpre.next = None
        rsuc = rp.next
        rp.next = None

        # 3. 反转(lp, rp)之间的链表
        head, tail = reverse(lp, rp)

        # 4. 接上
        lpre.next = head
        tail.next = rsuc

        return dummy.next

if __name__ == '__main__':
    head = ListNode(1, next=ListNode(2, next=ListNode(3, next=ListNode(4, next=ListNode(5)))))
    result = Solution().reverseBetween(head, 2, 4)
    print(result)




